package com.heima.datastructure.heap;

/**
 * <strong>堆</strong>
 * <ul>
 *     <li>堆是一种基于完全二叉树的数据结构</li>
 *     <li>完全二叉树
 *         <ul>
 *             <li>完全二叉树要保证前面n - 1层都是满，最后一层可以瞒可以不满</li>
 *             <li>完全二叉树的最后一层的叶子节点必须是从左往右依次添加得来的</li>
 *             <li>完全二叉树中任意父节点与子节点的索引关系：
 *                 <ul>
 *                     <li>索引1开始</li>
 *                     <ol>
 *                         <li>父节点索引为i，=> 左子节点：2i，右子节点：2i + 1</li>
 *                         <li>左子节点索引为i，=> 右子节点：i + 1，父节点：floor(i / 2)</li>
 *                     </ol>
 *                     <li>索引0开始</li>
 *                     <ol>
 *                         <li>父节点索引为i，=> 左子节点：2i + 1，右子节点：2i + 2</li>
 *                         <li>左子节点索引为i，=> 右子节点：i + 1，父节点：floor((i - 1) / 2)</li>
 *                     </ol>
 *                 </ul>
 *             </li>
 *             <li>所以完全二叉树可以用数组存储，普通二叉树也可以，缺失的节点用null表示</li>
 *         </ul>
 *     </li>
 *     <li>大顶堆：大顶堆中任意一个节点C与其父节点P满足：P.value >= C.value，所以根节点就是大顶堆中value最大的节点</li>
 *     <li>小顶堆：小顶堆中任意一个节点C与其父节点P满足：P.value <= C.value，所以根节点就是大顶堆中value最小的节点</li>
 * </ul>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/5 17:16
 */
public interface Heap<E extends Value> {

    /**
     * 建堆
     */
    void heapify();

    /**
     * 往堆尾部新增元素
     * @param value 新增元素
     * @return 是否新增成功
     */
    boolean offer(E value);

    /**
     * 获取堆顶元素并删除，然后重构
     * @return 堆顶元素
     */
    E poll();

    /**
     * 获取指定索引处的元素并删除，然后重构
     * @param index 索引
     * @return 指定索引处的元素
     */
    E poll(int index);

    /**
     * 获取堆顶元素
     * @return 堆顶元素
     */
    E peek();

    /**
     * 获取指定索引处的元素
     * @param index 索引
     * @return 指定索引处的元素
     */
    E peek(int index);

    /**
     * 替换堆顶元素
     * @param value 新堆顶元素
     */
    void replace(E value);

    /**
     * 判断堆是否为空
     * @return 为空返回true
     */
    boolean isEmpty();

    /**
     * 判断堆是否为满
     * @return 为满返回true
     */
    boolean isFull();

    /**
     * 获取当前堆的大小
     * @return 堆的大小
     */
    int size();

    /**
     * 扩容
     * @param capacity 扩展到多少容量
     */
    void expansion(int capacity);
}
